package com.as3.timbot.iso
{
	import com.as3.timbot.data.collections.PQueue;
	import com.as3.timbot.events.ArrayEvent;
	
	import flash.events.EventDispatcher;
	import flash.utils.getTimer;
	import flash.events.Event;

	public class Astar
	{
	
	//===============================================
	//====astarAS Object=============================
	//An awesome pathfinding algorithm
	public static var PATHFOUND:String = "path_found";
	private var __dispatch:EventDispatcher;
	private var limit:Number;
	private var maxSearchTime:Number;
	private var closed:Array;
	private var preventClipping:Boolean;
	private var keepSearching:Boolean;
	private var now:Number;
	private var map:Object;
	private var s:Object;
	private var goal:Object;
	private var pq:PQueue;
	private var open:Array;
	
	public function Astar() {
		//'limit' is the number of tiles allowed in the priority queue at once. Lower means faster but gives a less precise path.
		limit = 200;
		//This is the maximum amount of time in miliseconds that we are willing to wait for a path to be found
		maxSearchTime = 1700;
		closed = new Array();
		//if 'prevenClipping' is true, then a path will not go diagonal across or between blocked tiles. It goes around.
		preventClipping = true;
		__dispatch = new EventDispatcher();
	}
	public function addEventListener(ev:String,handle:Function):void
	{
		__dispatch.addEventListener(ev,handle);
	}
	public function setPreventClipping(value:Boolean) {
		preventClipping = value;
	}
	public function setLimit(newLimit:Number) {
		limit = newLimit;
	}
	public function setMaxSearchTime(newSearchTime:Number) {
		maxSearchTime = newSearchTime;
	}
	private function findHeuristic(x:Number, y:Number):Number {
		var dx = Math.abs(x-goal.x);
		var dy = Math.abs(y-goal.y);
		///why 1.41??? This is the distance of moving between one tile and another diagonally
		//This should stay the same for isometric tiles, who always have the same aspect ratio
		var val1 = Math.min(dx, dy)*1.41;
		var val2 = Math.max(dx, dy)-Math.min(dx, dy);
		return val1+val2;
	}
	private function cost(who:Object, newx:Number, newy:Number):Number
	{
		
		var val:Number = 1;
		
		var diffx:Number = who.x-newx;
		var diffy:Number = who.y-newy;
		var nextWho:Object = map.map[newx][newy];
		
		
		var whoTerrain:String = who.terrain;//Sound to String????
		var whoNextTerrain:String = nextWho.terrain;
	
		if (!whoTerrain) {
			whoTerrain = map.terrain.block;
			return Number.MAX_VALUE;
		}
		if (!whoNextTerrain) {
			whoNextTerrain = map.terrain.block;
			return Number.MAX_VALUE;
		}
		
		var transitionCost:Number = map.terrain[whoTerrain][whoNextTerrain];
		
		if (!transitionCost) {
			trace("---")
			trace(whoTerrain)
			trace(whoNextTerrain)
			return Number.MAX_VALUE;
		}
		if (diffx != 0 && diffy != 0) {
			
			val = 1.41;///again with 1.41????
			if (preventClipping) {
				var xsign:Number = (diffx)/Math.abs(diffx);
				var ysign:Number = (diffy)/Math.abs(diffy);
				var cell1x:Number = who.x-xsign;
				var cell1y:Number = who.y;
				var cell1:Object = map.map[cell1x][cell1y];
				var cell2x:Number = who.x;
				var cell2y:Number = who.y-ysign;
				var cell2:Object = map.map[cell2x][cell2y];
				if (cell1.solid || cell2.solid) {
					val = Number.MAX_VALUE;
				}
			}
		}
		val *= transitionCost;
		
		if (who.solid) {
			val = Number.MAX_VALUE;
		}
		
		return val;
	}
	private function checkNode(newx:Number, newy:Number, who:Object) 
	{
		
		var nameOb:Object = map.map[newx][newy];
		var gx:Number = goal.x;
		var gy:Number = goal.y;
		var g:Number = who.g+cost(who, newx, newy);
		
		if (who.x == gx && who.y == gy) {
			//////////////////////////////////////////////////////////////////
			keepSearching = false;//stops checking at the goal tile - should fire an event instead....t.w.
			//////////////////////////////////////////////////////////////////
		}
		if (!nameOb.exists) {
			//doesnt exist yet, so add it
			if (typeof map.map[newx][newy] == "object") {
				addOpen(newx, newy, g, who);
			}
		} else if (!nameOb.solid) {
			//exists already, see if the new g is less than the original g
			if (g<nameOb.g) {
				//this is a better g
				nameOb.parent = who;
				nameOb.g = g;
				nameOb.f = nameOb.h+g;
				var f:Number = nameOb.f;
				if (nameOb.where == "open") {
					pq.setPriority(nameOb.id, f);
				} else if (nameOb.where == "closed") {
					//Remove it from closed
					//This piece is rarely EVER used
					trace("========In Closed========");
					for (var j = 0; j<closed.length; ++j) {
						//closed[j].name == name
						if (closed[j] == nameOb) {
							closed.splice(j, 1);
						}
					}
				}
			}
		}
	
	}
	private function buildPath():Array
	{
	
		var parent:Object = map.map[goal.x][goal.y].parent;
		var path:Array = new Array();
		while (parent != null) {
			path.push([parent.x, parent.y]);
			parent = parent.parent;
		}
		path.reverse();
		path.shift();
		path.push([goal.x, goal.y]);
		return path;
	}
	///checks all the nodes surrounding the current one for comparisons
	private function expandNode() 
	{
	 	
		var who:Object = pq.removeTop();//get the top object from the priority queue
		
		//counter clockwise
		var nodex:Number = who.x;
		var nodey:Number = who.y;
		var whoName:Object = map.map[nodex][nodey];
		//
		//if one of the following nodes turns out to be the 'goal' node, checkNode will set the 'keepChecking' 
		//variable to false.  This ends the operation in the Search method below, causing the path to be
		//returned to the calling method
		checkNode(nodex-1, nodey+1, whoName);
		checkNode(nodex+1, nodey-1, whoName);
		checkNode(nodex-1, nodey-1, whoName);
		checkNode(nodex+1, nodey+1, whoName);
		checkNode(nodex+1, nodey, whoName);
		checkNode(nodex, nodey-1, whoName);
		checkNode(nodex-1, nodey, whoName);
		checkNode(nodex, nodey+1, whoName);
		
		//move to closed array
		who.where = "closed";
		closed.push(who);
		if (!keepSearching) {//keepSearching value is set in checkNode...kinda hacky....t.w.
		
			var myEvent:ArrayEvent = new ArrayEvent(Astar.PATHFOUND);
			myEvent.setArray(buildPath());
			__dispatch.dispatchEvent(myEvent);
			//trace (buildPath());
		}
	}
	private function addOpen(x:Number, y:Number, g:Number, parent:Object) {
		
		var h:Number = findHeuristic(x, y);//gets distance from currently inspected tile to destination tile
		var f:Number = g+h;//g - sum of distance scores for all visited tiles
		var ob:Object = map.map[x][y];//gets the tile being referenced
		ob.x = x;
		ob.y = y;
		ob.g = g;//score of all visited tiles
		ob.h = h;//heuristic score
		ob.f = f;//current tile score
		ob.parent = parent;
		ob.exists = true;
		ob.where = "open";
		var id = pq.insert(ob, f);//f is set as the priority in the queue
		ob.id = id;//an id number is returned by the queue and associated with the object
		
	
	}
	public function search(theMap:Object):Object
	{
		
		now = getTimer();
		//get a copy of the map
		map = theMap.clone();
		//delete pq;
		pq = null;
		
		//gets the starting tile and the ending tile from the map
		s = map.s;
		goal = map.g;
		pq = new PQueue();
		pq.setLimit(limit);
		
		addOpen(s.x, s.y, 0, null);//adds the starting tile to the priority queue
		
		keepSearching = true;//a global boolean used to keep a search loop running
		var solutionFound:Boolean = true;
		
		while (keepSearching) {
			//this is a bit of a problem I think...should be event based, rather than using the 'keepSearching' variable
			expandNode();//this could be a problem in as3 - expandNode only returns upon completion
			
			if (getTimer()-now>maxSearchTime) {
				//kill search
				trace("no solution");
				keepSearching = false;//breaks the operation on TimeOut...t.w.
				solutionFound = false;
			}
		}
		var searchTime = (getTimer()-now);
		//return {pathFound:solutionFound, path:thePath, searchTime:searchTime};
		return {pathFound:solutionFound, searchTime:searchTime};
	}


	}
}